package main

import "fmt"

func main() {
	arr := []int{113, 22, 13, 431, 52}
	tree := build(arr)
	tree.upDate(0, 4, 22)		//arr[0, 4]区间全部加+22
	tree.upDate(1, 3, -12)		//arr[1, 3]区间全部减-12
	fmt.Println(tree.query(1, 2))	//查询arr[1, 2]区间和
}
/*
	树状数组操作(区间更新, 区间查询)
*/
type Tree struct {
	c1, c2 []int	//c1 是 b1[i]差分数组的树状数组, c2 是 b2[i]=i*b1[i]的树状数组
	length int	//树状数组的长度=原数组元素个数+1
}
func build(arr []int) *Tree {
	length  := len(arr); b1, b2 := make([]int, length), make([]int, length); b1[0] =arr[0]
	for i:=1; i<length; i++ {b1[i]= arr[i]-arr[i-1]}	//获取差分数组b1[i]
	for i:=1; i<=length; i++ {b2[i-1]=i*b1[i-1]}		//获取b2[i] = i*b1[i], 因为我这里是从0开始的b2[i-1]=i*b2[i-1]
	tree := &Tree{make([]int, length+1), make([]int, length+1), length+1}
	tree.init(b1, b2); return tree //用b1，和b2 建立树状数组 可以O(n) 建立两棵树
}
func (this *Tree)init(b1, b2 []int) {  //O(n)建立 c1[i] 和 c2[i] 树状数组
	for i, j := 1, 0; i<this.length; i++ {
		this.c1[i] += b1[i-1]; this.c2[i] += b2[i-1]; j = i + lowBit(i)
		if j < this.length {this.c1[j] += this.c1[i]; this.c2[j] += this.c2[i]}
	}
}
func (this *Tree)upDate(l, r, v int) {this.up(l, v); this.up(r+1, -v)}
func (this *Tree)up(x, v int) {x++; for p := x; x < this.length; x += lowBit(x) {this.c1[x] += v; this.c2[x] += p * v}}
func (this *Tree)query(l, r int) int {return this.pre(r)-this.pre(l-1)}
func (this *Tree)pre(v int) int {
	if v < 0 {return 0}; ans1, ans2, n := 0, 0, v+1
	for v++; v>0; v -= lowBit(v) {ans1+=this.c1[v]; ans2+=this.c2[v]}
    /*
        n                n         n
        ∑ arr[i] = (n+1)*∑ b1[i] - ∑ i*b2[i]
       i=1              i=1       i=1
    */
	return (n+1)*ans1 - ans2
}
func lowBit(x int) int {return x&-x}